#include<iostream>
#include<vector>
#include<algorithm>


using std::cout;
using std::vector;
using std::swap;

std::ostream& operator<<(std::ostream& oss,vector<int>vec)
{
    for(const auto &i:vec)
    {
        oss<<i<<" ";
    }
    return oss;
}

int partition(vector<int>& vec,int low,int high)
{
    int key =vec[low];
    while(low<high)
    {
        while(low<high&&vec[high]>=key)
        {
            --high;
        }
        if(low<high)
        {
            vec[low++]=vec[high];
        }
        while(low<high&&vec[low]<=key)
        {
            ++low;
        }
        if(low<high)
        {
            vec[high--]=vec[low];
        }
    }
    vec[low]=key;
    return low;
}

void sort(vector<int> & vec,int low,int high)
{
    if(low<high)
    {
        int pos = partition(vec,low,high); 
        sort(vec,low,pos-1);
        sort(vec,pos+1,high);
    }
}

void fastsort(vector<int> &vec)
{
    int left=0;
    int right=vec.size()-1;
    sort(vec,left,right);
    cout<<vec;
}

void insert(vector<int>& vec)
{
    //插入排序
    int size =vec.size();
    for(int i=1;i<size;++i)
    {
        int j=i-1;
        int key=vec[i];
        while(j>=0&&vec[j]>key)
        {
            vec[j+1]=vec[j];
            --j;
        }
        vec[j+1]=key;
    }
}

void shellcore(vector<int> &nums,int gap,int i)
{
    int insert=nums[i];
    int j;
    for(j=i-gap;j>=0&&nums[j]>insert;j -= gap)
    {
        nums[j+gap]=nums[j];
    }
    nums[j+gap]=insert;
}

void xier(vector<int> & nums)
{
    int len =nums.size();
    for(int gap= nums.size()/2;gap>0;gap/=2)
    {
        for(int i=gap;i<len;++i)
        {
            shellcore(nums,gap,i);
        }
    }
}

void heapify(vector<int>& nums, int size,int idx)
{
    int left = idx*2+1;
    int right = idx*2+2;
    int max =idx;
    if(left<size-1&&nums[left]>nums[max]){
        max = left;
    }
    if(right<size&&nums[right]>nums[max]){
        max = right;
    }
    if(max!=idx)
    {
        swap(nums[idx],nums[max]);
        heapify(nums,size,max);
    }
}
void makeheap(vector<int>&nums,int n)
{
    for(int i=(n-2)/2;i>=0;--i) 
    {
        heapify(nums,n,i);
    }
}
void heapsort(vector<int>& nums)
{
    int size = nums.size();
    makeheap(nums,size);
    for(int i=size-1;i>0;i--)
    {
        swap(nums[0],nums[i]);
        heapify(nums,i,0);
    }
}

//选择排序
void chooseSort(vector<int>& nums)
{
    int size =nums.size();
    for(int i=0;i<size-1;++i)
    {
        int tmp = i;
        for(int j=i+1;j<size;++j)
        {
            if(nums[j]<nums[tmp])
            {
                tmp=j;
            }
        }
        int num = nums[i];
        nums[i]=nums[tmp];
        nums[tmp]=num;
    }
}

//冒泡排序
void bubblesort(vector<int> nums)
{
    for(int i=0;i<nums.size()+1;++i)
    {
      bool  flag=false;
        for(int j=0;j<nums.size()-i-1;++j)
        {
            if(nums[j]>nums[j+1])
            {
                swap(nums[j]>nums[j+1];
                flag =true;
            }
        }
        if(!flag) break;
    }
}

void insertSort(vector<int>& nums)
{
    int size =nums.size();
    for(int i=1;i<size;++i)
    {
        int j=i-1;
        int tmp = nums[i];
        while(j>=0&&nums[j]>tmp)
        {
            nums[j+1]=nums[j];
            --j;
        }
        nums[j+1]=tmp;
    }
}

void mergesort(vector<int> &ans ,vector<int>& copy,int start,int end)
{
    int mid = start+(end-start)>>1;
    int low = start;
    int end1 = end;
    int low1 =mid+1;
    mergesort(ans,copy,low,mid);
    mergesort(ans,copy,low1,end);
    int idx=start;
    while(low<mid&&low1<end)
    {
        copy[idx++]=ans[low]<ans[low1]?ans[low++]:ans[low1++];
    }
    while(low<=mid)
    {
        copy[idx++]=ans[low++];
    }
    while(low1<=end)
    {
        copy[idx++]=ans[low1++];
    }
    for(int i=start;i<=end;++i)
    {
        ans[i]=copy[i];
    }
}

int main()
{
    vector<int> srot(100);
    for(int i=0;i<100;++i)
    {
        srot[i]=100-i;
    }
    //insert(srot);
    // xier(srot);
    //heapsort(srot);
    vector<int> copy(srot.size(),0);
    mergesort(sort,copy,0,srot.size()-1);
    cout<<srot<<"\n";
    //快速排序
}
